#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣739. 每日温度
// 【难度】中等
// 【提交】2025 9 18 https://leetcode.cn/problems/daily-temperatures/submissions/663836171/
// 【标签】单调栈
class Solution_LC0739 {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> s;
        
        for(int i = 0; i < n; ++i) {
            while(!s.empty() && temperatures[i] > temperatures[s.top()]) {
                int prev_index = s.top();
                ans[prev_index] = i - prev_index;
                s.pop();
            }
            s.push(i);
        }
        return ans;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，
 * 其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 * 模型：单调栈（Monotonic Stack），用于高效找到下一个更大元素的位置。
 * 
 * 二、标准解法状态设计
 * 使用单调栈存储尚未找到更高温度的日期索引。栈中元素对应的温度保持递减顺序。
 * 对于每个新温度，与栈顶元素比较，若更高则计算等待天数并弹出栈顶，直到栈为空或栈顶温度不低于当前温度。
 * 
 * 三、你的实现思路
 * 使用单调栈方法，从左到右遍历温度数组，维护一个存储索引的栈，栈中索引对应的温度递减。
 * 对于每个温度，弹出所有比它低的温度对应的索引，并计算等待天数。
 * 
 * 四、逐行注释（带细节提醒）
 * vector<int> ans(n);        // 初始化结果数组，默认值为0
 * stack<int> s;             // 创建单调栈，存储尚未找到更高温度的日期索引
 * for(int i = 0; i < n; ++i) {  // 遍历每一天的温度
 *     while(!s.empty() && temperatures[i] > temperatures[s.top()]) { // 当前温度高于栈顶温度
 *         int prev_index = s.top(); // 获取栈顶元素的索引
 *         ans[prev_index] = i - prev_index; // 计算等待天数
 *         s.pop();          // 弹出已处理的元素
 *     }
 *     s.push(i);            // 将当前索引入栈
 * }
 * 
 * 五、正确性证明
 * 单调栈维护了尚未找到更高温度的日期索引，且栈中索引对应的温度递减。
 * 当遇到更高温度时，可以确定栈中所有低于当前温度的元素的下一个更高温度就是当前温度。
 * 算法保证了每个元素只入栈和出栈一次，正确性由单调栈性质保证。
 * 
 * 六、复杂度
 * 时间：O(n)，每个元素最多入栈和出栈一次。
 * 空间：O(n)，最坏情况下栈存储所有元素。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 时间复杂度低，只需一次遍历；
 *   - 代码简洁，实现高效；
 *   - 利用单调栈特性，避免暴力枚举。
 * 缺点：
 *   - 栈操作可能对初学者不易理解；
 *   - 未处理输入为空的情况（但题目保证 n>=1）。
 * 
 * 八、改进建议
 * 1. 可以添加提前判断：if (temperatures.empty()) return {};
 * 2. 使用更明确的变量名（如 stack 代替 s）来增强可读性；
 * 3. 对于教学场景，可以添加注释解释为什么栈中温度要保持递减顺序。
 * 
 * 九、一句话总结
 * 单调栈是解决"下一个更大元素"类问题的经典方法，你的实现准确且高效，能够熟练运用这一技巧解决相关问题。
 */